package com.backpack;

import java.util.Arrays;

public class LastStoneWeightII0111_1049 {
    public int lastStoneWeightII(int[] stones) {
        /**
         * 思路，将stones分割成尽可能相等的两堆石头，碰撞相减即为结果
         */
        int sum = Arrays.stream(stones).sum();
        int backpack = sum /2;

        //01背包问题，背包大小为backpack，
        //dp[i] 表示容量为i的背包，最大价值（重量）为dp[i];
        int[] dp = new int[backpack+1];

        //初始化
        for (int i = 0; i < backpack + 1; i++) {
            dp[i] = i >= stones[0] ? stones[0] : 0;
        }


        for (int i = 1; i < stones.length; i++) {
            for (int j = backpack; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);
            }
        }
        return (sum - dp[backpack] - dp[backpack]);


    }
}
